import java.util.Deque;
import java.util.LinkedList;

/**
* @description: 918. 环形子数组的最大和
* @author hewei
* @date 2022/9/19 14:35
* @version 1.0
*/

public class MaxSubarraySumCircular {

    public static void main(String[] args) {
        int[] nums = {3,1,3,2,6};
        System.out.println(new MaxSubarraySumCircular().maxSubarraySumCircular(nums));
    }

    public int maxSubarraySumCircular1(int[] nums) {
        int n = nums.length;
        int[] dpMax = new int[n];
        dpMax[0] = nums[0];
        int max = dpMax[0];
        int sum = nums[0];
        for (int i = 1; i < n; i++) {
            sum += nums[i];
            dpMax[i] = Math.max(dpMax[i - 1] + nums[i], nums[i]);
            max = Math.max(max, dpMax[i]);
        }
        int min = n > 1 ? nums[0] : 0;
        int last = min;
        for (int i = 1; i < n - 1; i++) {
            last = Math.min(last + nums[i], nums[i]);
            min = Math.min(min, last);
        }
        return Math.max(sum - min, max);
    }

    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] sum = new int[2 * n];
        sum[0] = nums[0];
        for (int i = 1; i < 2 * n; i++) {
            sum[i] = sum[i - 1] + nums[i % n];
        }
        int r = 1;
        Deque<Integer> queue = new LinkedList<>();
        queue.add(0);
        int ans = sum[0];
        while (r < sum.length) {
            if (!queue.isEmpty() && r - queue.peek() > n) queue.poll();
            ans = Math.max(ans, sum[r] - (queue.isEmpty() ? 0 : sum[queue.peek()]));
            while (!queue.isEmpty() && sum[queue.peekLast()] > sum[r]) queue.pollLast();
            queue.add(r);
            ++r;
        }
        return ans;
    }
}
